#pragma once
#include "ArcNode.hpp"

namespace Kama
{
    template <typename Key, typename Value>
    class ArcLfu
    {
    public:
        ArcLfu(int capacity, int transformThresold) : m_capacity(capacity), m_ghostCapacity(capacity), m_transformThresold(transformThresold)
        , min_freq(INT8_MAX)
        {
            initList();
        }

        bool put(const Key& key, const Value& value)
        {
            if (m_capacity <= 0)
            {
                return false;
            }
            std::lock_guard<std::mutex> lck(mtx);
            auto it = mainMap.find(key);
            if (it != mainMap.end())
            {
                return updateExistingNode(it->second, value);
            }
            
            return addNewNode(key, value);
        }

        bool get(const Key& key, Value& value)
        {
            std::lock_guard<std::mutex> lck(mtx);
            auto it = mainMap.find(key);
            if (it != mainMap.end())
            {
                updateFreq(it->second);
                value = it->second->getValue();
                return true;
            }
            return false;
        }

        Value get(const Key& key)
        {
            Value value;
            get(key, value);
            return value;
        }

        bool checkGhost(const Key& key)
        {
            auto it = ghostMap.find(key);
            if (it != ghostMap.end())
            {
                removeFromGhost(it->second);
                ghostMap.erase(it);
                return true;
            }
            return false;
        }

        void addCapacity()
        {
            ++m_capacity;
        }

        bool subtractCapacity()
        {
            if (m_capacity <= 0)
            {
                return false;
            }
            if (mainMap.size() == m_capacity)
            {
                removeLongestUnuse();
            }
            --m_capacity;
            return true;
        }
    private:
        void initList()
        {
            ghostHead = std::make_shared<ArcNode<Key, Value>>();
            ghostTail = std::make_shared<ArcNode<Key, Value>>();
            ghostHead->m_next = ghostTail;
            ghostTail->m_pre = ghostHead;
        }

        bool updateExistingNode(std::shared_ptr<ArcNode<Key, Value>> node, const Value& value)
        {
            node->setValue(value);
            updateFreq(node);
            return true;
        }

        bool addNewNode(const Key& key, const Value& value)
        {
            if (mainMap.size() == m_capacity)
            {
                removeLongestUnuse();
            }
            if (freqMap.find(1) == freqMap.end())
            {
                freqMap[1] = std::list<std::shared_ptr<ArcNode<Key, Value>>>();
            }
            auto node = std::make_shared<ArcNode<Key, Value>>(key, value);
            freqMap[1].push_back(node);
            mainMap[key] = node;
            min_freq = 1;
            return true;
        }

        void removeLongestUnuse()
        {
            auto it = freqMap.find(min_freq);
            if (it != freqMap.end())
            {
                auto node = it->second.front();
                int key = node->getKey();
                it->second.pop_front();
                if (it->second.empty())
                {
                    freqMap.erase(it->first);
                    // 更新最小频率 ???
                    min_freq = INT8_MAX;
                    for (const auto& pair : freqMap)
                    {
                        if (pair.first < min_freq)
                        {
                            min_freq = pair.first;
                        }
                    }
                }
                mainMap.erase(key);

                if (ghostMap.size() == m_ghostCapacity)
                {
                    removeOldestNode();
                }
                addToGhost(node);
            }
        }

        void updateFreq(std::shared_ptr<ArcNode<Key, Value>> node)
        {
            int oldFreq = node->getAccess();
            node->increseAccess();
            int newFreq = node->getAccess();
            freqMap[oldFreq].remove(node);
            if (freqMap[oldFreq].empty())
            {
                freqMap.erase(oldFreq);
                // 如果最小频次链表为空，则更新最小频次
                if (min_freq == oldFreq)
                {
                    min_freq = newFreq;
                }
            }
            if (freqMap.find(newFreq) == freqMap.end())
            {
                freqMap[newFreq] = std::list<std::shared_ptr<ArcNode<Key, Value>>>();
            }
            freqMap[newFreq].push_back(node);
        }

        void removeFromGhost(std::shared_ptr<ArcNode<Key, Value>> node)
        {
            if (!node)
            {
                return;
            }
            node->m_pre.lock()->m_next = node->m_next;
            node->m_next->m_pre = node->m_pre;
            node->m_next = nullptr;
        }   

        void removeOldestNode()
        {
            auto node = ghostHead->m_next;
            if (node != ghostTail)
            {
                removeFromGhost(node);
                ghostMap.erase(node->getKey());
            }
        }

        void addToGhost(std::shared_ptr<ArcNode<Key, Value>> node)
        {
            if (!node)
            {
                return;
            }
            node->m_pre = ghostTail->m_pre;
            node->m_next = ghostTail;
            ghostTail->m_pre.lock()->m_next = node;
            ghostTail->m_pre = node;
            ghostMap[node->getKey()] = node;
        }
    private:
        std::unordered_map<Key, std::shared_ptr<ArcNode<Key, Value>>> mainMap;
        std::unordered_map<Key, std::shared_ptr<ArcNode<Key, Value>>> ghostMap;
        std::unordered_map<int, std::list<std::shared_ptr<ArcNode<Key, Value>>>> freqMap;
        std::shared_ptr<ArcNode<Key, Value>> ghostHead;
        std::shared_ptr<ArcNode<Key, Value>> ghostTail;
        std::mutex mtx;
        int min_freq;
        int m_capacity;
        int m_ghostCapacity;
        int m_transformThresold;
    };
}